package cn.dai.test;

import org.junit.Test;

public class ArrayTest {

    // 杨辉三角形  案例联系
    @Test
    public void pascalTriangleDemo(){
        // 杨辉三角形  外围的长度不限制 (不要低于5)
        int[][] pascalTriangle = new int[10][];

        // 名字太长 声明一个简写引用一下
        int[][] tri = pascalTriangle;

        for (int i = 0; i < tri.length; i++) {

            // 声明内围的数组
            tri[i] = new int[i + 1];
            // 连续赋值 每一行，也就是每一组数组的头和尾都是1
            tri[i][0] = tri[i][i] = 1;

            // 对既不是头也不是尾的内部元素进行赋值
            for (int j = 1; j < tri[i].length - 1 ; j++) {
                tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j];
            }
        }

        // 打印查看
        for (int i = 0; i < tri.length; i++) {
            for (int j = 0; j < tri[i].length; j++) {
                System.out.print(tri[i][j]+"\t");
            }
            System.out.println();
        }
    }

    // 一维数组：求最大最小值，平均值，总和
    // 求最大值
    static int getMaximum(int[] array){
        // 设置游标
        int max = array[0];
        // 因为已经设置第一个赋值给了游标 从第二个开始遍历
        for (int i = 1; i < array.length; i++) {
            // max = array[i] > max ? array[i] : max;
            max = Math.max(array[i], max);
        }
        return max;
    }

    // 求最小值
    static int getMinimum(int[] array){
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            // min = array[i] < min ? array[i] : min;
            min = Math.min(array[i], min);
        }
        return min;
    }

    // 求和
    static int getSummation(int[] array){
        int sum = 0;
        for (int element : array) {
            sum += element;
        }
        return sum;
    }

    // 求平均值
    static double getAverage(int[] array){
        double sum = 0.0;
        for (int element : array) {
            sum += element;
        }
        return sum / array.length;
    }

    // 数组复制
    @Test
    public void arrayCopy01(){
        int[] array = {1,3,5,7,9};

        // 先复制长度
        int[] array2 = new int[array.length];

        for (int i = 0; i < array2.length; i++) {
            // 复制元素
            array2[i] = array[i];
        }
    }

    // 数组反转
    static int[] reverse1(int[] array){
        // 遍历一半长度进行元素交换
        for (int i = 0; i < array.length / 2; i++) {
            int temp = array[i];
            array[i] = array[array.length - 1 - i];
            array[array.length - 1 - i] = temp;
        }
        return array;
    }
    static int[] reverse2(int[] array){
        // 头尾双向交换
        for ( int i = 0,j = array.length -1; i < j ; i++,j--) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
        return array;
    }

    // 线性查找和二分查找

    // 线性查找
    static int linearSearch(int[] array,int target){
        for (int i = 0; i < array.length; i++) {
            if (target == array[i]) return i;   // 找到直接返回索引
        }
        return -1; // 找不到 返回-1
    }

    // 二分查找
    static int binarySearch(int[] array,int target){
        int start = 0;
        int end = array.length -1;

        while ( start <= end ){
            int mid = (start + end) / 2; // 每次二分都在不断变化的中轴游标
            if (target == array[mid]) return mid; // 碰上了正好直接返回
            else if (target > array[mid]) start = mid + 1; // 目标位置大于中轴，起始位置前推
            else end = mid + 1; // 反之后退
        }
        return -1;
    }

    // 冒泡排序和快速排序

    // 冒泡排序
    static int[] bubbleSort(int[] array){

        for (int i = 0; i < array.length -1; i++) {

            for (int j = 0; j < array.length -1; j++) {

                if (array[j] > array[j + i]){
                    int temp = array[i];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        return array;
    }

    // 快速排序
    static void quickSort(int[] arr,int start,int end){
        int i,j,temp,t;
        if(start > end) return;
        i = start;
        j = end;
        //temp就是基准位
        temp = arr[start];

        while (i < j) {
            //先看右边，依次往左递减
            while (temp <= arr[j] && i<j) j--;

            //再看左边，依次往右递增
            while (temp>=arr[i]&&i<j) i++;

            //如果满足条件则交换
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }

        }
        //最后将基准为与i和j相等位置的数字交换
        arr[start] = arr[i];
        arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, start, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, end);
    }

}
